<?php
/**
 * @title 1534. 统计好三元组 + 剪枝优化
 * @author start2004
 */


class Solution {

    /**
     * @param Integer[] $arr
     * @param Integer $a
     * @param Integer $b
     * @param Integer $c
     * @return Integer
     */
    function countGoodTriplets($arr, $a, $b, $c) {
        /**
         * @since 2020-08-03 键值keys
         */
        $keys = array_keys($arr);

        /**
         * @since 2020-08-03 排序
         */
        array_multisort($arr, SORT_ASC, SORT_NUMERIC, $keys);
        // return [$arr, $keys];

        /**
         * @since 2020-08-03 结果集
         */
        $result = 0;

        /**
         * @since 2020-08-03 遍历寻找`i`可能性
         */
        for($i=0, $len=count($arr); $i<$len; $i++){
            /**
             * @since 2020-08-03 键值keyI, 值valI
             */
            $keyI = $keys[$i];
            $valI = $arr[$i];

            /**
             * @since 2020-08-03 逆向`j`
             */
            for ($j=$i-1; $j>=0; $j--){
                $keyJ = $keys[$j];
                $valJ = $arr[$j];

                /**
                 * @since 2020-08-03 超出范围
                 */
                if($valI-$valJ>$a){
                    break;
                } else {
                    /**
                     * @since 2020-08-03 i<j
                     * @since 2020-08-03 |arr[i] - arr[j]| <= a
                     */
                    if($keyJ>$keyI){
                        /**
                         * @since 2020-08-03 查找k
                         */
                        $result += self::find($i, $j, $len, $arr, $keys, $b, $c);
                    } else {}
                }
            }

            /**
             * @since 2020-08-03 正向`j`
             */
            for($j=$i+1; $j<$len; $j++){
                $keyJ = $keys[$j];
                $valJ = $arr[$j];

                /**
                 * @since 2020-08-03 超出范围
                 */
                if($valJ-$valI>$a){
                    break;
                } else {
                    /**
                     * @since 2020-08-03 i<j
                     * @since 2020-08-03 |arr[i] - arr[j]| <= a
                     */
                    if($keyJ>$keyI){
                        /**
                         * @since 2020-08-03 查找k
                         */
                        $result += self::find($i, $j, $len, $arr, $keys, $b, $c);
                    } else {}
                }
            }
        }

        /**
         * @return
         */
        return $result;
    }

    /**
     * @title 匹配`k`
     * @author start2004
     * @since 2020-08-03 Created
     *
     * @param int $i
     * @param int $j
     * @param int $len
     * @param array $arr
     * @param array $keys
     * @param int $b
     * @param int $c
     *
     * @return int
     */
    public function find($i = 0, $j = 0, $len = 0, $arr = [], $keys = [], $b = 0, $c = 0){
        $count = 0;

        /**
         * @since 2020-08-03 2个点
         */
        $keyI = $keys[$i];
        $valI = $arr[$i];
        $keyJ = $keys[$j];
        $valJ = $arr[$j];

        /**
         * @since 2020-08-03 逆向`k`
         */
        for ($k=$j-1; $k>=0; $k--){
            $keyK = $keys[$k];
            $valK = $arr[$k];

            /**
             * @since 2020-08-03 超出范围
             */
            if($valJ-$valK>$b){
                break;
            } else {
                /**
                 * @since 2020-08-03 j<k
                 * @since 2020-08-03 |arr[j] - arr[k]| <= b
                 */
                if($keyK>$keyJ){
                    /**
                     * @since 2020-08-03 条件匹配
                     * |arr[i] - arr[k]| <= c
                     */
                    if(abs($valI-$valK) <= $c){
                        $count++;
                    } else {}
                } else {}
            }
        }

        /**
         * @since 2020-08-03 正向`k`
         */
        for ($k=$j+1; $k<$len; $k++){
            $keyK = $keys[$k];
            $valK = $arr[$k];

            /**
             * @since 2020-08-03 超出范围
             */
            if($valK-$valJ>$b){
                break;
            } else {
                /**
                 * @since 2020-08-03 j<k
                 * @since 2020-08-03 |arr[j] - arr[k]| <= b
                 */
                if($keyK>$keyJ){
                    /**
                     * @since 2020-08-03 条件匹配
                     * |arr[i] - arr[k]| <= c
                     */
                    if(abs($valI-$valK) <= $c){
                        $count++;
                    } else {}
                } else {}
            }
        }

        /**
         * @return
         */
        return $count;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.01.php
 */
$datas = [
    [[3,0,1,1,9,7], 7, 2, 3],
    [[1,1,2,2,3], 0, 0, 1],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->countGoodTriplets($data[0], $data[1], $data[2], $data[3]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
